/**
 * https://leetcode.cn/submissions/detail/585102655/
 * 310. 最小高度树
 * Medium, 黄伟杰 2024.12.05
 * DFS
 */

class Solution
{
    void dfs(int sta, vector<int> &dist, vector<int> &parent, const vector<vector<int>> &gs) // 计算长度
    {
        for (auto &g : gs[sta])
        {
            if (dist[g] < 0)
            {
                dist[g] = dist[sta] + 1;
                parent[g] = sta;
                dfs(g, dist, parent, gs);
            }
        }
    }
    int findlong(int sta, vector<int> &parent, const vector<vector<int>> &gs)
    {
        int n = gs.size();
        vector<int> dist(n, -1);
        dist[sta] = 0;
        dfs(sta, dist, parent, gs);
        int maxdist = 0;
        int node = -1;
        for (int i = 0; i < n; i++)
        {
            if (dist[i] > maxdist)
            {
                maxdist = dist[i];
                node = i;
            }
        }
        return node;
    }

public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges)
    { // 设两个叶子节点的最长距离为 maxdist，可以得到结论最小高度树的高度为 maxdist/2
        if (n == 1)
            return {0};
        vector<vector<int>> gs(n); // 建图
        for (auto &edge : edges)
        {
            gs[edge[0]].emplace_back(edge[1]);
            gs[edge[1]].emplace_back(edge[0]);
        }
        vector<int> parent(n, -1);
        //=0到最最远的结点
        int x = findlong(0, parent, gs);
        // x结点的最远结点
        int y = findlong(x, parent, gs);
        // 找路径
        vector<int> path;
        parent[x] = -1;
        while (y != -1)
        {
            path.emplace_back(y);
            y = parent[y];
        }
        int cnt = path.size();
        if (cnt % 2 == 0)
        {
            return {path[cnt / 2 - 1], path[cnt / 2]};
        }
        else
            return {path[cnt / 2]};
    }
};